package main

import "fmt"

func main() {
	coins := []int{1, 2, 5}
	amount := 11
	// coins := []int{2}
	// amount := 3
	// coins := []int{1, 2147483647}
	// amount := 2

	// coins := []int{1, 2, 5}
	// amount := 100

	fmt.Println(coinChange(coins, amount))
}

// 内存溢出
func coinChangeQ(coins []int, amount int) int {
	if amount == 0 {
		return 0
	}

	q := []int{}
	number := 0
	for _, v := range coins {
		t := amount - v
		if t > 0 {
			q = append(q, amount-v)
		} else if t == 0 {
			return 1
		}
	}

	if len(q) == 0 {
		return -1
	}

	for len(q) > 0 {
		number++
		s := len(q)
		tmp := []int{}
		for i := 0; i < s; i++ {
			for _, v := range coins {

				t := q[i] - v
				if t > 0 {
					tmp = append(tmp, t)
				} else if t == 0 {
					return number + 1
				} else {
					return -1
				}

			}
		}
		q = tmp
	}

	return number
}

// dp[i] = min(dp[i-1],dp[i-2],dp[i-5])+1
func coinChange(coins []int, amount int) int {
	dp := make(map[int]int)
	dp[0] = 0

	for _, v := range coins {
		if v < amount {
			dp[v] = 1
		}
	}

	for i := 0; i <= amount; i++ {
		 
		}
	}

	return dp[amount]
}
